This invention relates to packet-based data networks. More particularly, this invention relates to the exchange of routing information between routers in such a network.
In packet-based data networks such as the Internet, routers xe2x80x9ctalkxe2x80x9d to each other to exchange routing information. Specifically, a router will announce the path it will use to get to a particular destination to each of its peer routers. Each router will thus know the path that its peer routers will take in sending a packet to a particular destination. Routing protocols, running on the routers, are used to exchange such information between routers. A routing protocol can be an Interior Gateway Protocol (IGP) or an Exterior Gateway Protocol (EGP). An IGP is used for routing within an administrative domain such as within a corporate backbone network or within a network that is owned by one company and has a unified administrative control over how routing is done. Generally such routing is metric-based in that the goal in routing between two points within an administrative domain is to find the route with the lowest cost, where cost may, for example, be distance or some other parameter than can be assigned to a link between routers. Examples of common routing protocols used within an IGP are the Routing Information Protocol (RIP), the Open Shortest Path First (OSPF) protocol, and the Intermediate System to Intermediate System (ISxe2x80x94IS) protocol. The advantageous property of such IGPs is that they are guaranteed to always achieve a stable routing within the network that is consistent with the network""s configuration. The difference between the different routing protocols lies in the nature of the messages passed between routers. Since an IGP is used within a network that is owned or controlled by a single organization, no hostility exists between the owners of the routers within the network that might otherwise affect the willingness of a particular router in another network to accept traffic from a router owned by another.
An EGP is used to exchange routing information between autonomous administrative domains. Thus, border, or edge, routers that might link, for example, an autonomous ATandT network with an autonomous Sprint network, need to communicate via an EGP rather than an IGP. Unlike a single autonomous system in which routing can be metric based, routing between autonomous systems needs to be policy based. Each autonomous system may in fact want to protect itself from being used by others who are not paying for its use. Thus, one autonomous system may restrict routing through it from a competitor""s system since it doesn""t want such competitor""s customers to use its resources, even though such routing would be the xe2x80x9cshortestxe2x80x9d path. EGPs, unlike metric-based IGPs, are thus policy based because autonomous systems will not always be able to agree as to the best path to a specified destination. As a result, an EGP is much more complicated to administer since it involves expressing a policy of how an administrative domain wants to interact with the rest of the world.
The Border Gateway Protocol (BGP) is currently the only interdomain routing protocol employed on the Internet (see, e.g., Y. Rekhter and T. Li, xe2x80x9cA border gateway protocolxe2x80x9d, RFC 1771 [BGP version 4], 1995; J. W. Stewart, BGP4, Inter-Domain Routing in the Internet, Addison-Wesley, 1998; and B. Halabi, Internet Routing Architectures, Cisco Press, 1997). The BGP allows each autonomous system to independently formulate its own routing policies, and it allows these policies to override distance metrics in favor of policy concerns. However, routing policies of autonomous systems can conflict with each other. Inconsistencies in routing policies can result in several problems such as the inability to find a stable routing plan. Thus, as a change at one router occurs, information is exchanged with its peers that causes a second router to change its routing and exchange information with its peer routers, etc., etc., eventually causing the first router to change its routing again, then the second and so forth. Such a protocol is said to diverge and cause persistent route oscillations. Thus, with the BGP, edge routers between autonomous systems could continue to only exchange information without ever agreeing upon a stable routing plan. Such a situation could in fact have a catastrophic effect in the global Internet resulting in improperly routed traffic, and possibly even causing xe2x80x9cgridlockxe2x80x9d on the Internet with the amount of routing information being transferred from router to router. The latter could slow the network down to a crawl and, in a worst case situation, cause a xe2x80x9cmeltdownxe2x80x9d of the Internet. Further, an autonomous system on the network has no ability to determine the cause of the routing problems since it only has local information available to it. Even further, even if it did, no one autonomous system has the ability to correct oscillations caused by inconsistency of routing policies between autonomous systems.
The problems associated with the prior art are solved by the routing protocol of the present invention. This new routing protocol, referred to herein as the Simple Path Vector Protocol (SPVP), extends the BGP by adding a new attribute to the routing messages sent by an edge router to its peers in different autonomous sytems. This additional attribute is a path history which is dynamically computed at each edge router as the routing path to a particular destination is changed. This path history attribute is thus sent by a router to its peers together with the sending router""s path to that destination. Protocol oscillations caused by policy conflicts produce paths whose histories contain cycles. By observing the dynamic path history that is computed at an edge router as a received routing message from a peer router that contains a history attribute is processed, a cycle can be identified in the newly computed history and associated with a policy conflict at that receiving edge router""s associated autonomous system. In further accord with the present invention, the protocol automatically suppresses as a permitted path to that destination those paths whose histories contain cycles.